#include<iostream>
#include<vector>

using namespace std;


class Solution {
public:
    void duplicateZeros(vector<int>& arr) 
    {
        int len = arr.size();
        int cur = 0;
        int dest = -1;
        while (dest < len-1)
        {
            if (arr[cur])
            {
                ++dest;
            }
            else
            {
                if (dest + 2 == len)
                {
                    arr[len - 1] = 0;
                    cur--;
                    break;
                }
                else
                {
                    dest += 2;
                }
            }
            ++cur;
        }
        while (cur >= 0)
        {
            if (arr[cur])
            {
                arr[dest] = arr[cur];
                cur--;
                dest--;
            }
            else
            {
                arr[dest] = arr[cur];
                arr[--dest] = arr[cur];
                cur--;
                dest--;
            }
        }
    }
};
//int main()
//{
//    vector<int> v = { 1,0,2,3,0,4 };
//    Solution S;
//    S.duplicateZeros(v);
//    for(int i = 0; i < v.size(); i++)
//    {
//        cout << v[i] <<" ";
//    }
//    return 0;
// }


//class Solution {
//public:
//    void duplicateZeros(vector<int>& arr) {
//        int len = arr.size();
//        int cur = 0;
//        int dest = -1;
//        while (cur < len)
//        {
//            if (arr[cur])
//            {
//                ++dest;
//            }
//            else
//                dest += 2;
//            if (dest >= len - 1) break;
//            ++cur;
//        }
//        if (dest == len)
//        {
//            dest -= 2;
//            arr[len - 1] = 0;
//            cur--;
//        }
//        while (cur >= 0)
//        {
//            if (arr[cur])
//            {
//                arr[dest] = arr[cur];
//                cur--;
//                dest--;
//            }
//            else
//            {
//                arr[dest] = 0;
//                arr[--dest] = 0;
//                cur--;
//                dest--;
//            }
//        }
//    }
//};

//
//int main()
//{
//    const int N = 2E+6;
//    int n, m;
//    cin >> n >> m;
//    vector<int> v(N);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    while (m--)
//    {
//        int j = 0;
//        cin >> j;
//        cout << v[j - 1] << endl;
//    }
//
//    return 0;
//}